/**
 * @a https://leetcode.cn/problems/max-area-of-island/
 */

#include "../../common.h"


class Solution {
    vector<vector<bool>> visited;
    
private:
    int maxAreaOfIsland_aux(const vector<vector<int>>& grid, int i, int j){
        int area = 1;
        static int dx[4] = {0,0,1,-1};
        static int dy[4] = {1,-1,0,0};
        queue<pair<int,int>> que;
        que.push({i,j});
        visited[i][j] = true;
        int row = grid.size(), col = grid[0].size();
        while(que.size()){
            auto [a,b] = que.front();
            que.pop();
            for(int i = 0; i < 4; ++i){
                int x = a + dx[i], y = b + dy[i];
                if(x >= 0 && x < row && y >= 0 && y < col 
                    && visited[x][y] == false && grid[x][y] == 1)
                {
                    que.push({x,y});   
                    visited[x][y] = true;
                    ++area;
                }

            }
        }
        return area;
    }
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int row = grid.size();
        if(row == 0) return 0;
        visited.resize(row);
        int col = grid[0].size();
        for(auto& line:visited){
            line.resize(col,false);
        }
        int max = 0;
        for(int i = 0; i < row; ++i){
            for(int j = 0; j < col; ++j){
                if(grid[i][j] == 1 && visited[i][j] == false){
                    int tmp = maxAreaOfIsland_aux(grid, i, j);
                    max = max >  tmp? max:tmp;
                }
            }
        }
        return max;
    }
};